package leetcode.editor.cn;

/**
 * 希尔排序,https://www.cnblogs.com/chengxiao/p/6104371.html
 */
public class AShellSort implements AIOrder{
    // 交换法
//    @Override
    public void sort1(int[] nums) {
        for (int gap = nums.length/2; gap > 0; gap = gap/2) {
            for (int i = gap; i < nums.length; i++) {
                int j = i;
                while (j-gap >= 0) {
                    if (nums[j] < nums[j-gap]) {
                        swap(nums, j, j-gap);
                    }
                    j -= gap;
                }
            }
        }
    }

    // 移动法
    @Override
    public void sort(int[] nums) {
        for (int gap = nums.length/2; gap > 0; gap = gap/2) {
            for (int i = gap; i < nums.length; i++) {
                int temp = nums[i];
                int j = i;
                if (temp < nums[j-gap]) {
                    while (j-gap >= 0 && temp < nums[j-gap]) {
                        nums[j] = nums[j-gap];
                        j -= gap;
                    }
                    nums[j] = temp;
                }
            }
        }
    }

    public void swap(int[] nums, int first, int second) {
        nums[first] ^= nums[second];
        nums[second] ^= nums[first];
        nums[first] ^= nums[second];
    }

    public static void main(String[] args) {
        AIOrder order = new AShellSort();
        int[] nums = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        order.sort(nums);
        System.out.println("end");
    }
}
